package com.tucc.hello.leetcode.no1_400.no1_200.no81_100.no99;

import com.tucc.hello.tree.Main;
import com.tucc.hello.tree.TreeNode;

import java.util.Arrays;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root = Main.makeTree(Arrays.asList(1, 3));
        solution.recoverTree(root);
        TreeNode.printMiddleOrder(root);
    }


    TreeNode pre = null, err1, err2;

    public void recoverTree(TreeNode root) {
        middleScanTree(root);
        if (err1 != null && err2 != null) {
            int temp = err1.val;
            err1.val = err2.val;
            err2.val = temp;
        }
    }

    public void middleScanTree(TreeNode root) {
        if (root != null) {
            if (root.left != null) {
                middleScanTree(root.left);
            }
            if (pre != null) {
                if (pre.val >= root.val) {
                    if (err1 == null) {
                        err1 = pre;
                    }
                    err2 = root;
                }
            }
            pre = root;
            if (root.right != null) {
                middleScanTree(root.right);
            }

        }
    }

}
